/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
 var exist = function(board, word) {
    var h=board.length;
    var w=board[0].length;
    var visited=new Array(h);
    for(let i=0;i<h;i++){
        visited[i]=new Array(w).fill(0);
    }
    var directions=[[-1,0],[0,-1],[1,0],[0,1]];
    function search(x,y,target){
        console.log(x,y,visited);
        if(target==word.length){
            return true;
        }
        for(let dir of directions){
            let nx=x+dir[0];
            let ny=y+dir[1];
            if(nx>=0&&ny>=0&&nx<h&&ny<w&&visited[nx][ny]==0&&board[nx][ny]==word[target]){
                visited[nx][ny]=1;
                if(search(nx,ny,target+1)){
                    return true;
                }
                else{
                    visited[nx][ny]=0;
                }
            }
        }
        return false;
    }
    for(let i=0;i<h;i++){
        for(let j=0;j<w;j++){
            if(board[i][j]==word[0]){
                visited[i][j]=1;
                if(search(i,j,1)){
                    return true;
                }
                else{
                    visited[i][j]=0;
                }
            }
        }
    }
    return false
};


console.log(exist([["C","A","A"],["A","A","A"],["B","C","D"]],
"AAB"));

// 执行用时：
// 120 ms
// , 在所有 JavaScript 提交中击败了
// 47.18%
// 的用户
// 内存消耗：
// 41.3 MB
// , 在所有 JavaScript 提交中击败了
// 68.77%
// 的用户